﻿#include <iostream>
using namespace std;

const int n = 6;
const int MAX = 1000;

typedef struct {											//定义辅助数组的元素类型
	int lowcost;
	int adjvex;
} Element;

void Prim(int arc[n][n], int w) {							//从顶点w开始构造最小生成树
	int i, j, k;
	int min;
	Element shortEdge[10];									//存储候选最短边集，假设最多10个顶点
	for(i = 0; i < n; i++) {								//初始化辅助数组shortEdge
		shortEdge[i].lowcost = arc[w][i];
		shortEdge[i].adjvex = w;
	}
	shortEdge[w].lowcost = 0;								//将顶点w加入集合U
	for(i = 0; i < n - 1; i++) {
		min = 100;											//假设权值均小于100
		for(j = 0; j < n; j++) {							//寻找最短边的邻接点k
			if((shortEdge[j].lowcost != 0) && (shortEdge[j].lowcost < min)) {
				min = shortEdge[j].lowcost;
				k = j;
			}
		}
		cout << shortEdge[k].adjvex << "--" << k << endl;	//输出最小生成树的边
		shortEdge[k].lowcost = 0;							//将顶点k加入集合U中
		for(j = 0; j < n; j++) {							//调整数组shortEdge[n]
			if(arc[k][j] < shortEdge[j].lowcost) {
				shortEdge[j].lowcost = arc[k][j];
				shortEdge[j].adjvex = k;
			}
		}
	}
}

int main() {
	int arc[n][n] = {
		MAX, 34, 46, MAX, MAX, 19,
		34, MAX, MAX, MAX, 12, MAX,
		46, MAX, MAX, 17, MAX, 25,
		MAX, MAX, 17, MAX, 38, 25,
		MAX, 12, MAX, 38, MAX, 26,
		19, MAX, 25, 25, 26, MAX
	};
	Prim(arc, 0);

	system("pause");
	return 0;
}
